package com.example.hot100;

import java.util.*;

/**
 * 给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
 *  candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
 *
 *  对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
 *
 *  示例 1：
 * 输入: candidates = [2,3,6,7], target = 7
 * 输出: [[7],[2,2,3]]
 *
 *  示例 2：
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 *
 *  示例 3：
 * 输入: candidates = [2], target = 1
 * 输出: []
 *
 *  示例 4：
 * 输入: candidates = [1], target = 1
 * 输出: [[1]]
 *
 *  示例 5：
 * 输入: candidates = [1], target = 2
 * 输出: [[1,1]]
 */
public class Leetcode39_CombinationSum {
    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;

        List<List<Integer>> res = new Solution().combinationSum(candidates, target);
        System.out.println(res);
    }

    static class Solution {
        /**
         * 先进行排序，然后剪枝优化
         *
         * @param candidates
         * @param target
         * @return
         */
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(candidates);
            dfs(candidates, target, new LinkedList<>(), res, 0);
            return res;
        }

        private  void dfs(int[] candidates, int target, Deque<Integer> singleRes, List<List<Integer>> res, int beginIndex) {
            if (beginIndex == candidates.length) return;
            if (target == 0) {
                res.add(new ArrayList<>(singleRes));
                return;
            }

            for (int i = beginIndex; i < candidates.length; i++) {
                if (target - candidates[i] >= 0) {
                    singleRes.push(candidates[i]);
                    dfs(candidates, target - candidates[i] , singleRes, res, i);
                    singleRes.pop();
                } else {
                    break;
                }
            }

        }

        /**
         * 未进行剪枝优化的回溯算法
         * @param candidates
         * @param target
         * @return
         */
        public List<List<Integer>> combinationSum1(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            dfs(candidates, target, new LinkedList<>(), 0, res, 0);

            return res;
        }

        /**
         * 表示当前在 candidates 数组的第 index位，已经组合的总和为sum，已经组合的列表为 singleRes
         * 在当前的函数中，每次我们可以选择跳过不用第 index 个数，即执行 dfs(candidates, target, singleRes, sum, index + 1)。
         * 也可以选择使用第 index 个数，即执行 dfs(candidates, target, singleRes, sum + candidates[index], index)
         * @param candidates
         * @param target
         * @param singleRes
         * @param sum
         * @param res
         * @param index
         */
        private void dfs(int[] candidates, int target, Deque<Integer> singleRes, int sum, List<List<Integer>> res, int index) {
            if (index == candidates.length) return;
            if (sum == target) {
                res.add(new ArrayList<>(singleRes));
                return;
            }

            dfs(candidates, target, singleRes, sum, res, index + 1); // 跳过当前index对应的数
            // 选择当前数
            if (sum + candidates[index] <= target) {
                singleRes.push(candidates[index]);
                dfs(candidates, target, singleRes, sum + candidates[index], res, index); // 每个数字可以被无限制重复选取，因此搜索的下标仍为 index
                singleRes.pop();
            }

        }

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            return combinationSum2(candidates, target);
        }
    }
}
